Many telecommunications network services providers and cable TV operators are showing significant interest in provisioning Video-on-Demand (VOD) services. These services are expected to grow significantly over time. Primary application areas include on-demand home entertainment, distance learning and training, and news-on-demand. These services require significant capital investments. In one extreme network configuration, a central server would broadcast all programs to all demand nodes, imposing very large bandwidth requirements on numerous links. In another extreme, a server would be installed at every node and all programs that might be requested would be stored at the node. The latter configuration would require a large number of servers and would incur large storage and processing costs.
The present invention considers a flexible configuration in which servers can be located in a subset of the nodes and a subset of the programs is assigned to each of the servers. In practice, the programs are aggregated into program families, where a program family includes multiple programs with the same characteristics. For example, children's movies may be represented by one family, action movies by another, etc. As used hereinbelow, a program family is referred to as a program.
Various related problems have been explored. A. Balakrishnan, T. L. Magnanti, and R. T. Wong, “A Decomposition Algorithm for Local Access Telecommunications Network Expansion Planning”, Operations Research, 43, 58-76, 1995, B. Li, M. J. Golin, G. F. Italiano, and X. Deng, “On the Optimal Placement of Web Proxies in the Internet”, Proceedings of IEEE INFOCOM 1999 Conference, V. 3, 1282-1290, 1999, O. E. Flippo, A. W. J. Kolen, A. M. C. A. Koster, and R. L. M. J. Van de Leensel, “A Dynamic Programming Algorithm for the Local Access Telecommunication Network Expansion Problem”, European Journal of Operational Research, 127, 189-202, 2000, T. Carpenter, M. Eiger, P. Seymour, and D. Shallcross, “Node Placement and Sizing for Copper Broadband Access Networks”, Annals of Operations Research, 106, 199-228, 2001, I. Cidon, S. Kutten, and R. Soffer, “Optimal Allocation of Electronic Content”, Computer Networks 40, 205-218, 2002, and C. A. Behrens, T. Carpenter, M. Eiger, H. Luss, G. Seymour, and P. Seymour, “Digital Subscriber Line Network Deployment Method”, U.S. Pat. No. 7,082,401, issued Jul. 25, 2006 present models and variations of dynamic programming algorithms for placing concentrators in traditional access networks and for placing equipment for diverse broadband services. Such equipment may include Digital Subscriber Line (DSL) Access Multiplexers for DSL services, Optical Network Units in Fiber-to-the-Curb networks and in cable networks, web proxies, etc. The algorithms presented in these references can be used to solve a special case of the present invention in which all programs are assigned to all servers. G. Dammicco, U. Mocci, and F. U. Bordoni, “Optimal Server Location in VOD Networks”, Global Telecommunications Conference (GLOBECOM) 1997, IEEE 1, 197-201, 3-8 Nov., 1997 present a simple model for server locations and program assignments in VOD tree networks. Their model partitions the tree nodes into levels where all nodes of the same level are equally far from node 0 in terms of number of hops. The model finds the optimal level where servers should be installed and the optimal subset of programs that should be assigned to servers at that level. The model is restrictive as all nodes at the selected level would have a server and the same subset of programs. T. Bektas, O. Oguz, and I. Ouveysi, “Designing Cost-Effective Content Distribution Networks”, Computers and Operations Research, article in press, expected to appear in 2007 (available online, 13 Oct. 2005) discuss a content distribution model for a logical tree network, where servers are directly connected to the central server and each of the demand nodes is directly connected to one of the servers. The resulting network configuration is limited to trees with a depth of two hops from the root node to the demand nodes.
The present invention uses a dynamic programming optimization method to determine optimal location of servers throughout a network with a general tree topology and optimal assignment of programs to each of these servers. Current state-of-the-art systems use ad-hoc heuristics and communications network managers' experience to design such flexible network configurations.